Information security is required to secure many types of transactions performed electronically using a wide range of computing and communication technologies. As consumers demand more flexible, convenient services, technologies such as wireless networks, paging infrastructures and smart cards are being deployed to support critical, information sensitive applications including account inquiries, electronic cash, secure communications and access control. One of the key features of each of these technologies is that they offer consumers the convenience of service anywhere, any time. The convenience offered to consumers results in a challenge for the vendors to create smaller and faster devices while providing a high level of security for information computed and transmitted.
Information security is provided through the application of cryptographic systems (commonly referred to as cryptosystems). The two main classes of cryptosystems are symmetric and public key. In a symmetric cryptosystem, two users wishing to participate in a secure transaction must share a common key. Therefore, each user must trust the other not to divulge the key to a third party. Users participating in a secure transaction using public key cryptosystems will each have two keys, known as a key pair. One of the keys is kept secret and is referred to as the private key, while the other can be published and is referred to as the public key. Typically, applications use a combination of both these classes of cryptosystems to provide information security. Symmetric technologies are typically used to perform bulk data encryption, while public key technologies are commonly used to perform key agreement, key transport, digital signatures and encryption of small messages.
Since the introduction of public key cryptosystems, there have been many implementations proposed. All of these public key systems are based on mathematical problems which are known to be hard, that is, it is thought that breaking a system is equivalent to solving a hard mathematical problem. These problems are generally easy to solve for numbers that are small in size, but become increasingly difficult as larger numbers are used. One of the differences among the systems is how large the numbers have to be so that the system is too hard to solve given present and anticipated computing power. This is typically linked to the length of the key and referred to as the key size. A system using a small key size while maintaining a high level of security is considered better, as it requires less information to be transmitted and stored.
Diffie-Hellman key agreement provided the first practical solution to the key distribution problem by allowing two parties to securely establish a shared secret over an open channel. The original key agreement protocol provides unauthenticated key agreement. The security is based on the discrete logarithm problem of finding integer x given a group generator a, and an element β, such that ax=β.
Rivest Shamir Adleman (RSA) was the first widely deployed realization of a public key system. The RSA system is a full public key cryptosystem and can be used to implement both encryption and digital signature functions. The security of the RSA cryptosystem depends on the difficulty of factoring the product of two large distinct prime numbers. To create a private key/public key pair, a user chooses two large distinct primes P and Q, and forms the product n=PQ. With knowledge of P and Q, the user finds two values e and d such that ((MYe)d mod n=M.
The public key of the user is the pair (e, n) while the private key is d. It is known that the recovery of d from and e and n requires the recovery of P and Q, and thus is equivalent to factoring n.
Elliptic curve cryptosystems are based on an exceptionally difficult mathematical problem. Thus, elliptic curve systems can maintain security equivalent to many other systems while using much smaller public keys. The smaller key size has significant benefits in terms of the amount of information that must be exchanged between users, the time required for that exchange, the amount of information that must be stored for digital signature transactions, and the size and energy consumption of the hardware or software used to implement the system. The basis for the security of the elliptic curve cryptosystem is the assumed intractability of the elliptic curve discrete logarithm problem. The problem requires an efficient method to find an integer k given an elliptic curve over a finite field, a point P on the curve, another point Q such that Q=kP.
In this system, the public key is a point (Q) on an elliptic curve (represented as a pair of field elements) and the private key is an integer (k). Elliptic curves are defined over an underlying field and may be implemented over the multiplicative group Fp, (the integers modulo a prime p) or characteristic 2 finite fields (F2 ∞, where m is a positive integer).
There are typically three levels in a cryptosystem, which are encryption, signatures, and certificates. These three levels can be implemented using the above mentioned systems or a combination thereof.
The first level of a cryptosystem involves encrypting a message between correspondent A and correspondent B. This level is vulnerable to attack since there is no way for correspondent A to verify whether or not correspondent B sent the message, or if a third party in the guise of correspondent B sent the message.
Therefore, the second level of signing a message was introduced. Correspondent B can sign the encrypted message using, for example, a hashing function to hash the original message. If correspondent A uses the same hashing function on the decrypted message and it matches the signature sent by correspondent B, then the signature is verified. However, a third party may act as an interloper. The third party could present itself to correspondent A as if it were correspondent B and vice versa. As a result, both correspondents would unwittingly divulge their information to the third party. Therefore, the signature verifies that the message sent by a correspondent is sent from that correspondent, but it does not verify the identity of the correspondent.
To prevent this type of attack, the correspondents may use a trusted third party (TTP) to certify the public key of each correspondent. The TTP has a private signing algorithm and a verification algorithm assumed to be known by all entities. The TTP carefully verifies the identity of each correspondent, and signs a message consisting of an identifier and the correspondent's public key. This is a simple example as to how a TTP can be used to verify the identification of the correspondent.
Some of the most significant emerging areas for public key cryptosystems include wireless devices. Wireless devices, including cellular telephones, two-way pagers, wireless modems, and contactless smart cards, are increasing in popularity because of the convenience they provide while maintaining a low cost and small form factor.
However, implementing the above mentioned cryptosystems requires computational power, which is limited on such wireless devices. Therefore, there is a need for a cryptosystem that provides all of the advantages as described above, but requires less power from the wireless device.